Insert

The only function we need which isn't easily defined as a reduction is Insert, which inserts an element into a sorted list. For example,

#math154#
Insert~Lessthan~3~[1, 2, 4, 5] = #tex2html_wrap_indisplay2645#[3#tex2html_wrap_indisplay2646#Insert#tex2html_wrap_indisplay2647#@@#tex2html_wrap_indisplay2648#<;SPMlt;< 986>>:#tex2html_wrap_indisplay2649#:}#tex2html_wrap_indisplay2650#<;SPMlt;< 987>>:#tex2html_wrap_indisplay2651#:}31, 2, 4, 5]  

Insert takes in an ordering as its first parameter, so we're not stuck with one particular order. It is defined directly in terms of the definition of lists.
#math155#
Insert~o~x~xs = xs~(Insert'~o~x)~(Singleton~x)  
Insert'~o~x~y~ys = o~x~y  
    ;SPMnbsp;;SPMnbsp;;SPMnbsp;;SPMnbsp;(Cons~x~(Cons~y~ys))  
    ;SPMnbsp;;SPMnbsp;;SPMnbsp;;SPMnbsp;(Cons~y~(Insert~o~x~ys))  

We can then define the function all this has been leading up to, #math156#Insertsort which takes an ordering and a list, and insert-sorts the list according to the ordering. For example,
#math157#
Insertsort~Lessthan~[2, 3, 1, 2] = #tex2html_wrap_indisplay2667# : #tex2html_wrap_indisplay2668##tex2html_wrap_indisplay2669#Foldr#tex2html_wrap_indisplay2670#@@<<#999#><<#1005#>#tex2html_wrap_indisplay2671#Insert#tex2html_wrap_indisplay2672#@@<<#1006#>#tex2html_wrap_indisplay2673#653>><<#1000#><<#1000#>#tex2html_wrap_indisplay2674#651>>647>><<#995#><<#1002#>#tex2html_wrap_indisplay2675#Insert#tex2html_wrap_indisplay2676#@@<<#1003#>#tex2html_wrap_indisplay2677#667>><<#996#><<#996#>#tex2html_wrap_indisplay2678#665>>645>>#tex2html_wrap_indisplay2679#! :}#tex2html_wrap_indisplay2680#[ ;SPMlt; 2#tex2html_wrap_indisplay2681##tex2html_wrap_indisplay2682##tex2html_wrap_indisplay2683##tex2html_wrap_indisplay2684#, 3, 1, 2]  

We can implement this as a fold:
#math158#
Insertsort~o = Foldr~(Insert~o)~Nil  

And so we've got sorted lists.
 
Interestingly, as we have implemented unbounded lists in TEX's mouth, this means we can implement a Turing Machine. So, if you believe the Church-Turing thesis, TEX's mouth is as powerful as any computer anywhere. Isn't that good to know?